package DoblePointer;//给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
// 
//
// 注意：字符串长度 和 k 不会超过 10⁴。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ABAB", k = 2
//输出：4
//解释：用两个'A'替换为两个'B',反之亦然。
// 
//
// 示例 2： 
//
// 
//输入：s = "AABABBA", k = 1
//输出：4
//解释：
//将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
//子串 "BBBB" 有最长重复字母, 答案为 4。
// 
// Related Topics 哈希表 字符串 滑动窗口 👍 505 👎 0


import java.util.HashMap;

//leetcode submit region begin(Prohibit modification and deletion)
class characterReplacement {
    public static int characterReplacement(String s, int k) {
        /***
         * 记录滑动窗口中数量最多的字符，数量记为n,滑动窗口长度记为l
         * 若 n+k >= l  说明这个窗口满足 替换后全为一种字符，此时长度即为窗口长度，窗口扩大
         * 否则窗口缩小
         * */
        int max = Integer.MIN_VALUE; // 最大子串长度
        HashMap<Character, Integer> calcul = new HashMap<>();  //字符计数
        int len = s.length();

        //特殊情况
        if(s==null||len==0){
            return 0;
        }else if(len==1){
            return 1;
        }


        char[] chars = s.toCharArray();
        int left = 0, right = 1;  //快慢指针
        char curLeft = chars[left];
        char curRight = chars[right];
        calcul.put(curLeft, calcul.getOrDefault(curLeft,0)+1);
        calcul.put(curRight, calcul.getOrDefault(curRight,0)+1);
        int l = right-left+1;   //滑动窗口长度
        while(right<len){
            int n = getMaxNum(calcul);
            if(n+k >= l){
                max = Math.max(l,max);
                if(right==len-1){
                    break;
                }
                char nextChar = chars[++right];
                calcul.put(nextChar,calcul.getOrDefault(nextChar,0)+1);
                l++;
            }else{
                char delLeft = chars[left++];
                calcul.put(delLeft, calcul.get(delLeft)-1);
                l--;
            }
        }
        return max;
    }

    static int getMaxNum(HashMap<Character, Integer> calcul){
        int max = Integer.MIN_VALUE;
        for (char ch :
                calcul.keySet()) {
            max = Math.max(calcul.get(ch),max);
        }
        return max;
    }

    public int characterReplacement1(String s, int k) {

        //字符串的长度
        int length = s.length();
        //用来存放对应字母的个数，比如字母A的个数是map[0],
        //字母B的个数是map[1]……
        int[] map = new int[26];
        int left = 0;//窗口左边的位置
        int maxSameCount = 0;  //窗口内曾经出现过相同字母最多的数量
        int right = 0;//窗口右边的位置
        //满足条件的最大窗口，也就是可以替换的最长子串的长度
        int maxWindow = 0;
        //窗口的左边先不动，移动右边的位置
        for (; right < length; right++) {
            //统计窗口内曾经出现过相同字母最多的数量
            maxSameCount = Math.max(maxSameCount, ++map[s.charAt(right) - 'A']);
            //如果相同字母最多的数量加上k还小于窗口的大小，说明其他的字母不能全部替换为
            //最多的那个字母，我们要缩小窗口的大小，顺便减去窗口左边那个字母的数量，
            //因为他被移除窗口了，所以数量要减去
            if (k + maxSameCount < right - left + 1) {
                map[s.charAt(left) - 'A']--;
                left++;
            } else {//满足条件，要记录下最大的窗口，
                maxWindow = Math.max(maxWindow, right - left + 1);
            }
        }
        return maxWindow;
    }

    public static void main(String[] args) {
        String s = "AABABBA";
        System.out.println(characterReplacement(s,2));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
